// c++ standard libraries
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

// c libraries
#include <cmath>

using namespace std;

//其中length为输入长度，num是包含n个互不相同元素值的向量，weight是包含元素值对应的权重的向量，index为递归调用时的索引(下标)
int WeightMedian(int length, vector<int> num, vector<double> weight, int index);

struct testCase {
    int length;
    vector<int> num;
    vector<double> weight;
};

int main() {

    testCase case1 = {
            .length=10,
            .num=vector<int>{719, 449, 446, 981, 431, 993, 919, 389, 549, 453},
            .weight=vector<double>{0.01757775, 0.02028202, 0.16863048, 0.07320842, 0.16283562, 0.16167665,
                                   0.14970060, 0.04095036, 0.12806645, 0.07707166}
    };

    testCase case2 = {
            .length=10,
            .num=vector<int>{13825, 28995, 18417, 92445, 86407, 90546, 46896, 14757, 89837, 18252},
            .weight=vector<double>{0.08720404, 0.09585595, 0.12070109, 0.02521966, 0.01221968, 0.12648725,
                                   0.13076193, 0.19128049, 0.15673069, 0.05353921}
    };

    testCase case3 = {
            .length=20,
            .num=vector<int>{70622, 73563, 24481, 9610, 52289, 90557, 35861, 22682, 54531, 63018, 32736, 56097,
                             56539, 8578, 38988, 86510, 85203, 99544, 74789, 93677},
            .weight=vector<double>{0.07241892, 0.05676781, 0.04709988, 0.10284543, 0.05305229, 0.02524795,
                                   0.01264511, 0.06271935, 0.07867683, 0.09960291, 0.00815778, 0.03618849, 0.05196861,
                                   0.00716533, 0.00654487, 0.02599975, 0.08601429, 0.01072407, 0.10110212, 0.05505821}
    };


    //测试代码将测试用例的三行数据分别导入length，num，和weight中
    //调用WeightMedian(length,num, weight,index)函数，函数内部使用cout输出得到的中位数，测试代码默认index初始值为0
    WeightMedian(case1.length, case1.num, case1.weight, 0);
    WeightMedian(case2.length, case2.num, case2.weight, 0);
    WeightMedian(case3.length, case3.num, case3.weight, 0);

    return 0;
}

// 其中length为输入长度，num是包含n个互不相同元素值的向量，weight是包含元素值对应的权重的向量，index为递归调用时的索引(下标)
// 复杂度: O(n) = 2n, 关键是每次枢轴的值
int WeightMedian(int length, vector<int> num, vector<double> weight, int index) {
    if (index == 0) {
        // weight[-2] = L_i
        // weight[-1] = R_i
        weight.push_back(0.5);
        weight.push_back(0.5);
    }
    double R_i = weight.back();
    weight.pop_back();
    double L_i = weight.back();
    weight.pop_back();

    int pivot_num = num.back();
    num.pop_back();
    double pivot_weight = weight.back();
    weight.pop_back();

    vector<int> left_num;
    vector<double> left_weight;
    vector<int> right_num;
    vector<double> right_weight;

    double left_weight_sum = 0.0, right_weight_sum = 0.0;
    for (int i = 0; i < (int) num.size(); i++) {
        if (num.at(i) < pivot_num) {
            left_num.push_back(num.at(i));
            left_weight.push_back(weight.at(i));
            left_weight_sum += weight.at(i);
        } else {
            right_num.push_back(num.at(i));
            right_weight.push_back(weight.at(i));
            right_weight_sum += weight.at(i);
        }
    }

    if (left_weight_sum + pivot_weight > L_i && right_weight_sum + pivot_weight > R_i) {
        cout << pivot_num << endl;
        return pivot_num;
    } else if (left_weight_sum + pivot_weight < L_i) {
        L_i = L_i - left_weight_sum - pivot_weight;
        right_weight.push_back(L_i);
        right_weight.push_back(R_i);
        WeightMedian((int) right_num.size(), right_num, right_weight, index + 1);
    } else if (right_weight_sum + pivot_weight < R_i) {
        R_i = R_i - right_weight_sum - pivot_weight;
        left_weight.push_back(L_i);
        left_weight.push_back(R_i);
        WeightMedian((int) left_weight.size(), left_num, left_weight, index + 1);
    }
    return 0;
}
